package main

// 计算s不同非空子序列的个数
// 10^9+7取余

// dp
// dp[i] 以s[i]结尾的子序列数目
// 	如果子序列只有s[i]这一字符，则只有一个方案
// 	至少两个字符的情况,枚举倒数第二个字符进行状态转移
// 		倒数第二个字符可以选s[0]/s[1]/..../s[i-1]
// 		dp[i] = dp[0] + dp[1] + ... + dp[i-1]
// 		需要解决重复计数的问题

func distinctSubseqII(s string) int {
	const mod int = 1e9 + 7
	last := make([]int, 26)
	for i := range last {
		last[i] = -1
	}
	n := len(s)
	f := make([]int, n)
	for i := range f {
		f[i] = 1
	}
	for i, c := range s {
		for _, j := range last {
			if j != -1 {
				f[i] = (f[i] + f[j]) % mod
			}
		}
		last[c-'a'] = i
	}
	var res int
	for _, i := range last {
		if i != -1 {
			res = (res + f[i]) % mod
		}
	}
	return res
}
